One of the main problems in quantum complexity theory is that ourunderstanding of the theory of QMA-completeness is not as rich as its classicalanalogue, the NP- completeness. In this paper we consider the clique problem ingraphs, which is NP- complete, and try to find its quantum analogue. We showthat, quantum clique problem can be defined as follows; Given a quantumchannel, decide whether there are k states that are distinguishable, with noerror, after passing through channel. This definition comes from reconsideringthe clique problem in terms of the zero-error capacity of graphs, and thenredefining it in quantum information theory. We prove that, quantum cliqueproblem is QMA-complete. In the second part of paper, we consider the sameproblem for the Holevo capacity. We prove that computing the Holevo capacity aswell as the minimum entropy of a quantum channel is NP-complete. Also, we showthese results hold even if the set of quantum channels is restricted toentanglement breaking ones.
展开▼
